// https://www.lintcode.com/problem/word-squares/description

// class Solution {
// public:
    /*
     * @param words: a set of words without duplicates
     * @return: all word squares
     */
     
// Input
// ["abat","baba","atan","atal"]
// Output
// []
// Expected
// [["baba","abat","baba","atal"],["baba","abat","baba","atan"]] 可以重复的？
     
    // void getPermutaion(vector<string> words, vector<string> perm, vector<vector<string>>& result, vector<bool> visited) {
    //     if (!perm.empty() && perm.size() == perm[0].size())
    //     {
    //         result.push_back(perm);
    //     }
    //     for (int i = 0; i < words.size(); ++i)
    //     {
    //         if (visited[i]) continue;
    //         visited[i] = true;
    //         perm.push_back(words[i]);
    //         getPermutaion(words, perm, result, visited);
    //         perm.pop_back();
    //         visited[i] = false;
    //     }
    // }
    // bool check(vector<string> words)
    // {
    //     if (words.size() != words[0].size()) return false;
    //     for (int i = 0; i < words.size(); ++i)
    //     {
    //         // for (int j = 0; j < words[0].size(); ++j)
    //         for (int j = i; j < words[i].size(); ++j)
    //         {
    //             if (words[j][i] != words[i][j])
    //             {
    //                 return false;
    //             }
    //         }
    //     }
    //     return true;
    // }
    // vector<vector<string>> wordSquares(vector<string> &words) {
    //     vector<vector<string>> result;
    //     vector<string> perm;
    //     vector<vector<string>> tmp;
    //     vector<bool> visited(words.size(), false);
    //     getPermutaion(words, perm, tmp, visited);
        
    //     for (vector<string> per: tmp)
    //     {
    //         // for (string p: per)
    //         // {
    //         //     cout << p << endl;
    //         // }
    //         if (check(per)) result.push_back(per);
    //     }
    //     return result;
    // }
    
// };


// 法一：回溯（他是从右边判断的，判断方块的右和底是否一样）
// class Solution {
// public:
//     /*
//      * @param words: a set of words without duplicates
//      * @return: all word squares
//     */     
//     vector<vector<string> > result;
//     map<string, vector<string> >prefix;
//     vector<string> storage; 
//     int num;
//     vector<vector<string> > wordSquares(vector<string> &words) {
//         if(words.size() == 0) {
//             return result;
//         }
//       for (auto w: words)
//       {
//           string tmp = "";
//           prefix[tmp].push_back(w); //初始化，""为所有的前缀
//           for (auto s: w)
//           {
//               tmp += s;
//               prefix[tmp].push_back(w);
//           }
//       }
//       num = words[0].size();
//       dfs(0);
//       return result;
//     }

//     // 剪枝，后面有一列构成的前缀没有那就false
//     bool check(int cur, string str) {
//         for (int i = cur + 1; i < num; ++i)
//         {
//             string tmp = "";
//             // for (int j = 0; j < num; ++j)
//             for (int j = 0; j < cur; ++j)
//             {
//                 tmp += storage[j][i];
//             }
//             tmp += str[i];
//             if (prefix[tmp].size() == 0) return false;
//         }
//         return true;
//     }

//     void dfs(int cur) {
//         if (cur == num)
//         {
//             result.push_back(storage);
//             return;
//         }
//         string pre = "";
//         for (auto s: storage)
//         {
//             pre += s[cur];
//         }
//         for (auto p: prefix[pre])
//         {
//             if (!check(cur, p)) continue;
//             storage.push_back(p);
//             dfs(cur + 1);
//             storage.pop_back();
//         }
//     }
// };

// 法二：Trie树
// class TrieNode {
// public:
//     TrieNode* children[26];
//     vector<int> indexes; //记录有哪些单词到了这个节点
//     TrieNode ()
//     {
//         for (int i = 0; i < 26; ++i)
//         {
//             children[i] = NULL;
//         }
//     }
// };

class Solution {
public:
    struct TrieNode {
        vector<int> indexes;
        vector<TrieNode*> children;
        TrieNode(): children(26, nullptr) {}
    };

    TrieNode* build(vector<string>& words)
    {
        TrieNode* root = new TrieNode();
        for (int i = 0; i < words.size(); ++i)
        {
            TrieNode* t = root;
            for (int j = 0; j < words[i].size(); ++j)
            {
                if (!t->children[words[i][j] - 'a'])      
                    t->children[words[i][j] - 'a'] = new TrieNode();
                t = t->children[words[i][j] - 'a'];
                t->indexes.push_back(i);
            }
        }
        return root;
    }

    // words out 不传引用会超时
    void helper(int level, vector<string>& words, vector<string>& out, vector<vector<string>>& res, TrieNode* root)
    {
        if (level == words[0].size()) {
            res.push_back(out);
            return;
        }
        string str = "";
        for (int i = 0; i < level; ++i)
        {
            str += out[i][level];
        }
        TrieNode* t = root;
        for (int i = 0; i < str.size(); ++i)
        {
          if (!t->children[str[i] - 'a']) return;
          t = t->children[str[i] - 'a'];
        }
        for (int i: t->indexes)
        {
            out[level] = words[i];
            helper(level + 1, words, out, res, root);
        }
    }
    vector<vector<string> > wordSquares(vector<string> &words) 
    {
        TrieNode* root = build(words);
        vector<vector<string>> res;
        if(words.size() == 0){
            return res;
        }
        vector<string> out(words[0].size()); //out[0] = w;这样就不用pop了
        for (string w: words) //需要手动初始化
        {
            out[0] = w;
            helper(1, words, out, res, root);
        }
        return res;
    }
};


